package examination_practice01;


import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;

class Mypoint{//定义二维点类
    double x;
    double y;
    public Mypoint(double x,double y){
        this.x=x;
        this.y=y;
    }
    //计算两点之间的距离
    public double getDistance(Mypoint Another_point){
        double dx=x-Another_point.x;
        double dy=y-Another_point.y;
        return Math.sqrt(dx*dx+dy*dy);
    }
}
public class DCClosestPair {
    private static double closestPair(Mypoint[] provide_points,int start,int end){
        //如果只有一个点或没有，则返回正无穷
        if (start>=end){
            return Double.POSITIVE_INFINITY;
        }
        //如果只有两个点，则直接计算它们的距离
        else if (end-start==1) {
            return provide_points[start].getDistance(provide_points[end]);
        }
        //否则，递归地进行分治计算
        else {
            Arrays.sort(provide_points,(o1,o2)->Double.compare(o1.x,o2.x));

            int mid=(start+end)/2;
            double leftDistance=closestPair(provide_points,start,mid);
            double rightDistance= closestPair(provide_points,mid+1,end);

            //比较左边和右边点对集中最近点地距离，取较小值
            double minDistance =Math.min(leftDistance,rightDistance);

            //中间区域的情况
            double middleDistance=findCrossInMiddleRegion(provide_points,start,end,mid,minDistance);
            minDistance=Math.min(minDistance,middleDistance);
            return minDistance;
        }
    }
    private  static double findCrossInMiddleRegion(Mypoint[] provide_points,int start,int end,int mid,double minDistance){
        //创建存储中间区域地列表
        List<Mypoint> middleRegion=new ArrayList<>();
        //根据x坐标将点对加入中间区域
        for (int i=start;i<=end;i++){
            if (Math.abs(provide_points[i].x-provide_points[mid].x)<minDistance){
                middleRegion.add(provide_points[i]);
            }
        }

        //根据y坐标对中间区域的点按照从小到大排序
        Collections.sort(middleRegion,(point1,point2)->Double.compare(point1.y,point2.y));

        int size=middleRegion.size();
        //在排序后的中间区域点寻找最近距离的点对
        for (int i=0;i<size-1;i++){
            for (int j=i+1;j<size && middleRegion.get(j).y-middleRegion.get(i).y<minDistance;j++){
                double distance=middleRegion.get(i).getDistance(middleRegion.get(j));
                if (distance<minDistance){
                    minDistance=distance;
                }
            }
        }
        return minDistance;
    }
    public static void main(String[] args){
        int n = 4;
        Mypoint[] points = new Mypoint[n];
        points[0] = new Mypoint(0, 0);
        points[1] = new Mypoint(1, 1);
        points[2] = new Mypoint(1, 1.5);
        points[3] = new Mypoint(3, 3);

        //Arrays.sort(points,(o1,o2)->Double.compare(o1.x,o2.x));

        //计算最接近点对的最小距离
        double minDistance=closestPair(points,0,n-1);
        System.out.printf("最短距离为：%.5f",minDistance);
    }

}
